package com.example.leetcode;

/**
 * 动态规划 ** 参考题解 ** 难点
 *  解码方法
 */
public class Demo0091 {

    /**
     * 上楼梯的复杂版
     * 如果连续的两位数符合条件，就相当于一个上楼梯的题目，
     */
    public int numDecodings(String s) {
        int len =s.length();
        if (len==0){
            return 0;
        }
        if (s.charAt(0)=='0'){
            return 0;
        }
        if (len==1){
            return 1;
        }
        //第一个肯定可以。非0
        int fun[]=new int[len];
        fun[0]=1;
        if (s.charAt(1)=='0'){
            if (s.charAt(0)<='2'){
                fun[1]=1;
            }else {
                return 0;
            }
        }else {
            if(s.charAt(0) == '1' || ((s.charAt(0) == '2') && s.charAt(1) <= '6')){
                fun[1]=2;
            }else {
                fun[1]=1;
            }
        }
        for (int i = 2; i <len; i++) {
            if (s.charAt(i)=='0'){
                //为0 能连
                if ((s.charAt(i-1) == '1' || ((s.charAt(i-1) == '2') && s.charAt(i) <= '6'))){
                    fun[i]=fun[i-2];
                }else {
                    //为0 不能连
                    return 0;
                }
            }else {
                if ((s.charAt(i-1) == '1' || ((s.charAt(i-1) == '2') && s.charAt(i) <= '6'))){
                    //不为0 能连
                    fun[i]=fun[i-1]+fun[i-2];
                }else {
                    //不为0 不能连
                    fun[i]=fun[i-1];
                }
            }
        }
        return fun[len-1];
    }


    public int numDecodings1(String s){
        final int length = s.length();
        if(length == 0) return 0;
        if(s.charAt(0) == '0') return 0;

        int[] dp = new int[length+1];
        dp[0] = 1;

        for(int i=0;i<length;i++){
            dp[i+1] = s.charAt(i)=='0'?0:dp[i];
            if(i > 0 && (s.charAt(i-1) == '1' || (s.charAt(i-1) == '2' && s.charAt(i) <= '6'))){
                dp[i+1] += dp[i-1];
            }
            int a[]=new int[]{};
        }

        return dp[length];
    }
}
